package com.study.algorithm.basicalsort.imp;

import com.study.algorithm.basicalsort.BasicalSort;
import com.study.algorithm.utils.ListUtil;

import java.util.List;

/**
 * 选择排序
 * 原理（以从小到大排序为例)
 * 由第一个开始扫描，每一轮都把当前一轮最小的值
 * 放到当前轮的最顶部位置
 */
public class SelectSortImpl implements BasicalSort {

    @Override
    public List<Integer> basicalSort(List<Integer> originList) {
        int size = originList.size();
        List<Integer> destList = ListUtil.DeepClone(originList);
        if (size <= 1) {
            return destList;
        }
        for (int i = 0; i < size; i++) {
            findMinToTop(destList, i, size);
        }
        return destList;
    }

    /**
     * 找到当前轮的最小值和其所在位置坐标
     * 与当前轮的顶部坐标值互换
     */
    private void findMinToTop(List<Integer> integers, int insertIndex, int size) {

        int minValue = 0;
        int minIdex = 0;

        for (int currIndex = insertIndex; currIndex < size; currIndex++) {
            int currVal = integers.get(currIndex);
            if (currVal < minValue || currIndex == insertIndex) {
                minValue = currVal;
                minIdex = currIndex;
            }
        }

        if (minIdex != insertIndex) {
            ListUtil.ExchangeValue(integers, minIdex, insertIndex);
        }

    }

}
